Collision detection in computer graphics typically refers to the computational problem of detecting the intersection of two or more objects. The topic is often discussed in connection with video games and other physical simulations. It has also applications in computer aided design (CAD), robotics, billiard game, nuclear physics, tracing of rays in high quality computer graphics, and other fields. While physical simulation needs to simulate real-world physics as precisely as possible, computer graphics of real time applications, such as video games, need to perform collision detection in real time and robustly. An individual subclass of collision is bouncing of rays in ray tracing, more precisely, a computational problem of detecting collision between secondary rays and scene objects.
Collision detection applications can run on variety of computing platforms, however the bouncing of ray tracing, associated with generating images, must specifically run on graphics computing system. A typical computer graphics system, with discrete graphics processing unit (GPU), is depicted in FIG. 1A. It consists of at least one CPU 101 that runs the application, and a discrete GPU 104 that generates images. They are connected by an interconnection network 102. There are two memories in the system. The system memory 105 is connected to the CPU by a memory management unit 103. The video memory 107 is connected to GPU. The display 106 is connected to GPU as well. Recently, a trend toward tighter integration between CPU and GPU has brought to the market the Multicores (termed also graphics enabled Multicores) FIG. 1B, consisting of multiple CPU cores 111 and multiple graphics cores 114, all on the same silicon chip. Such an integration on a single chip, including on silicon interconnect 112, removes the typical CPU-GPU communication bottleneck, and unifies the system memory 115 for both CPU and GPU cores. The memory management unit 113 connects the multicore to the system memory. The display interface 118 connects the display to graphics cores.
In high visual quality computer graphics, objects are represented by meshes of polygons while rays are represented by lines. Collision between a ray and a polygon can stand for (i) visibility, when a ray that is shot from a camera (primary ray) or its descendant ray (secondary ray) hits a polygon (aka object surface); or for (ii) illumination, when a polygon is hit by a ray that emits from a light source. In order to detect collision between ray and objects in the scene, a precise trajectory of the line must be calculated and intersection tests must be conducted between the ray's line and the polygons in the scene.
One problem is the high processing cost of intersection tests. For each frame, a rendering system must find the intersection points between millions of rays and millions of polygons. The cost of testing each ray against each polygon is prohibitive. A simplistic approach may create an impossible number of intersections. To reduce the number of ray/polygon intersection tests, accelerating structures are in use in the prior art, such as Octree, KD-tree, and bounding boxes. Acceleration structures are intended to reduce the amount of ray/object intersection tests by limiting the areas of tests to the ray's neighboring regions only. Nevertheless, the acceleration structure must be traversed for each ray, executing thousands of intersection tests along each ray, and typically taking 60%-70% of a frame. Moreover, construction of optimized structures is expensive and does not allow the real time frame rates that are imperative for dynamic scenes. Other weaknesses of acceleration structures stem from large memory footprints, and limited parallelism due to the centrality of the data base in a system.
As a consequence of the problems noted above, the prior art line/polygon collision detection suffers from poor performance, due to costly reconstruction and traversals of acceleration structures. Thus, there is a need in the art to devise a line/polygon collision detection method having a reduced amount of intersection tests, reduced traversals, and no or limited of reconstruction of complex acceleration structures.